1. Field of the Invention
The present invention is related generally to communications with host adapter integrated circuits, and in particular to methods of queuing hardware command blocks that are used in communicating tasks to one or more host adapter integrated circuits, or other devices.
2. Description of Related Art
Hardware control blocks, sometimes called sequencer control blocks or SCSI control blocks (SCBs), are typically used for transferring information between a software host adapter device driver in a host computer and a host adapter integrated circuit that controls operations of one or more peripheral devices. Methods for queuing SCBs are known to those of skill in the art. For example, see copending and commonly assigned U.S. patent application Ser. No. 07/964,532 entitled "Intelligent SCSI Bus Host Adapter Integrated Circuit," of Craig A. Stuber et al. filed on Oct. 16, 1992, which is incorporated wherein by reference in its entirety. See also copending and commonly assigned U.S. patent application Ser. No. 08/269,491 entitled "A Sequencer Control Block Array External To A Host Adapter Integrated Circuit" of B. Arlen Young, et al. filed on Jun. 30, 1994, and also U.S. Pat. No. 5,564,023 entitled "Method for Accessing A Sequencer Control Block By A Host Adapter Integrated Circuit" of B. Arlen Young issued on Oct. 8, 1996, each of which is incorporated herein by reference in its entirety.
Typically, the software host adapter device driver, that transmits SCBs to the host adapter integrated circuit, included an operating system specific module (OSM) and a hardware interface module (HIM) that both were maintained in the host computer system. The OSM knew nothing about the hardware in the host adapter integrated circuit and communicated with both the host computer operating system and the HIM. The HIM communicated only with the host adapter integrated circuit and the OSM. The OSM provided information for use in a SCB and sent that information to the HIM, which in turn built a SCB. Alternative methods for queuing the SCBs by the HIM and the host adapter integrated circuit are described in the patents referenced above and so are not repeated herein.
In another application illustrated in FIG. 1, a secondary microprocessor 105, e.g., an Intel i960 microprocessor receives a command for a virtual disk drive, e.g., a read command, or a write command to a RAID system, from a host computer(not shown) over host computer bus 115. Similar to the operations described above, in response to the virtual disk drive command, an OSM 101, that is executing on secondary microprocessor 105, sends information necessary to implement the virtual disk drive command to a HIM 102, that also executes on secondary microprocessor 105, and in turn transfers control to HIM 102. HIM 102 includes the information received from OSM 101 in a SCB or SCBs, that are built by HIM 102, to implement the virtual disk drive command.
HIM 102 manages a plurality of host adapter devices 120, 130, and a buffer memory controller device 140 that are on a secondary PCI bus 111, and configures each SCB for execution by a particular one of these devices. Secondary PCI bus 111 is coupled to secondary microprocessor 105 by a local bus to PCI bus interface circuit 110.
Buffer memory controller device 140 is, for example, an Adaptec AIC 7810 host adapter integrated circuit while host adapter devices 120 and 130 are each an Adaptec AIC-7880 host adapter integrated circuit. Each of host adapter integrated circuits 120, 130, and buffer memory controller device 140 includes an on-board processor, i.e., sequencers 125, 135 and 145, respectively, and scratch memory.
Communication between HIM 102 and host adapter integrated circuits 120, 130, and buffer memory controller device 140 is accomplished using an external memory bus 112 and random access memory 150. Specifically, HIM 102 reads and writes SCBs to a SCB array 155 in random access memory 150 via an external bus port 116 that is connected to random access memory 150 by external memory bus 112. Random access memory 150 is within the address spaces of devices 120, 130, 140, that are each connected to random access memory 150 via external memory bus 112.
Task requests from HIM 102 to host adapter devices 120, 130, and buffer memory controller device 140 are made via the SCBs. In this embodiment, HIM 102 writes the SCBs to one of 256 sites of SCB array 155 (FIG. 2) in RAM 150. The size of each site is 32 bytes. Each SCB written to a site in RAM 150 is executed by a sequencer in one of devices 120, 130, and 140. Similarly, when execution of the SCB is completed, HIM 102 receives the completed SCB from the site in RAM 150.
To manage the SCBs, a new SCB queue is maintained within SCB array 155 for each of devices 120, 130, and 140. Devices 120, 130, and 140 share a done SCB queue. Each SCB queue is a linked list of SCBs and has head and tail pointers that delimit the queue. The head and tail pointers are stored in SCB array site 255 (FIG. 2).
Both HIM 102 and the sequencer in the device can access SCBs in the new SCB queue for that device as well as the head and tail pointers in SCB site 255 for the queue. Thus, each SCB queue has two delimiters that are accessible by both a device driver and one of a plurality of devices.
When a SCB is placed in a queue, either the new SCB queue or the done SCB queue, the SCB is linked to the SCB at the end of the queue, using the tail pointer to identify the tail SCB. After appending the SCB to the SCB queue, the tail pointer in SCB site 255 is updated to point to the new end of the queue. If the queue was empty, there is no queued SCB to which to append the SCB. In this instance, the queue head pointer in SCB site 255 also must be updated to point to the SCB. These operations are performed by the party, either HIM 102 or the device sequencer, placing the SCB in the queue.
To remove a SCB from a queue, the queue head pointer is used to identify the first SCB in the queue. SCBs can be removed from any site in the queue, including the sites addressed by the head and tail pointers, i.e., the head SCB and the tail SCB, respectively. If the head SCB is removed, the head pointer must be updated. If the tail SCB is removed, the tail pointer must be updated. If a SCB at a position other than the head is removed, the pointer to the next SCB in the queue is relocated from the removed SCB to the SCB preceding the removed SCB in the queue.
FIG. 3 illustrates a new SCB queue 355 for host adapter device 130 within SCB array 155 that contains three SCBs 301 to 303. SCB 301 is stored in SCB site 5, SCB 302 in SCB site 37 and SCB 303 in SCB site 102.
Each of SCBs 301 to 303 includes a field Q.sub.-- NEXT. Field Q.sub.-- NEXT contains either a SCB site pointer with a pointer value that points to the next SCB site in new SCB queue 355, or a pointer value that indicates the end of new SCB queue 355.
Specifically, SCB 301 is linked to SCB 302 by a SCB site pointer having a value of 37 stored in field Q.sub.-- NEXT, and SCB 302 is linked to SCB 303 by a SCB site pointer having a value of 102 stored in field Q.sub.-- NEXT. The pointer in field Q.sub.-- NEXT of SCB 303 at the tail of new SCB queue 355 has a predefined value, e.g., the null value of 255, indicating that SCB 303 is the last SCB in new SCB queue 355.
Since SCB site pointer value 255 has been assigned as the null or invalid value, no SCB is ever loaded by HIM 102 into SCB array site 255 (FIG. 2). Therefore, this site is available for uses other than storing SCBs. In this embodiment, SCB array site 255 is used for saving queue head and tail pointers for the new SCB and done SCB queues, since array site 255 is accessible by both HIM 102 and all of sequencers 125, 135, and 145 in host adapter devices 120, 130, and buffer memory controller device 140, respectively. For example, head pointer 310 points to head SCB site 5 and tail pointer 311 points to tail SCB site 102.
HIM 102 might build new SCB queue 355 in the following matter. Initially, new SCB queue 355 is empty. This is reflected by head and tail pointer values of 255 (Not shown). HIM 102 builds SCB 301 to be executed by host adapter device 130 in response to information from OSM 101, and allocates SCB array site 5 in memory 150 for SCB 301. HIM 102 loads array site 5 with SCB 301, and loads head and tail pointers 310 and 311 with the value five to indicate that new SCB queue 305 contains a single SCB 301.
Later, HIM 101 builds two more SCBs 302 and 303 to be executed. HIM 101 allocates array sites 37 and 102 for these SCBs, and loads SCBs 302 and 303 into these sites. SCB 302 is linked to SCB 303 by loading 102 into field Q.sub.-- NEXT of SCB 302. Since SCB 303 will become the tail SCB of new SCB queue, HIM loads 255 into field Q.sub.-- NEXT of SCB 303. HIM appends two new SCBs 302 and 303 to new SCB queue 355 by loading thirty-seven into field Q.sub.-- NEXT of SCB 301. Finally, HIM 102 updates tail pointer 311 in SCB array site 255 to point to SCB site 102. Head pointer 310 is not updated, because new SCB queue 355 was not empty when two new SCBs 302 and 303 were queued. While this example considers new SCB queue 355, the construction of done SCB queue is similar except the operations described are performed by the device sequencer.
While HIM 102 is appending SCBs to new SCB queue 355, sequencer 135 can be removing SCBs from new SCB queue 355. Sequencer 135 scans new SCB queue 355 from head SCB 301 to tail SCB 303, looking for a SCB that is eligible for execution. Execution can be delayed because, for example, a device targeted by the SCB is already busy.
Specifically, sequencer 135 determines that new SCB queue 355 is not empty by checking head pointer 310 in SCB array site 255, and finding that head pointer 310 is not set to 255. Sequencer 135 uses head pointer 310 to locate head SCB 301 in new SCB queue 355.
If sequencer 135 finds that head SCB 301 cannot yet be executed, sequencer 135 reads the SCB site pointer in field Q.sub.-- NEXT of SCB 301 to locate the storage site of next SCB 302 in new SCB queue 355. If sequencer 135 finds that execution can begin for SCB 302, sequencer 135 removes SCB 302 from new SCB queue 355. Removal of SCB 302 is accomplished by moving the value of the SCB site pointer in field Q.sub.-- NEXT of SCB 302 to field Q.sub.-- NEXT of previous SCB 301. Thus, the value 102 is moved from field Q.sub.-- NEXT of SCB 302 at SCB array site 37 to field Q.sub.-- NEXT of SCB 301 at SCB array site 5. Neither head pointer 310 nor tail pointer 311 is changed by sequencer 135, because SCB 302 was neither at the head nor the tail of new SCB queue 355.
Later, when sequencer 135 is looking for another SCB to begin executing, sequencer 135 scans new SCB queue 355 again. If, for example, sequencer 135 finds that SCB 301 still cannot be started, sequencer 135 checks SCB 303. If SCB 303 can be started, sequencer 135 removes SCB 303 from new SCB queue 355. Since the SCB site pointer in field Q.sub.-- NEXT of SCB 303 has a value of 255, sequencer 135 recognizes that SCB 303 is at the tail of new SCB queue 355. Upon removing SCB 303 from new SCB queue 355, the new queue tail becomes SCB 301. Sequencer 135 moves the value of the SCB site pointer in field Q.sub.-- NEXT in SCB 303 to field Q.sub.-- NEXT in SCB 301, and loads SCB array site 5 into the tail pointer 311 at SCB site 255. Head pointer 310 is not changed.
Eventually, SCB 301 becomes eligible for execution, and sequencer 135 removes SCB 301 from new SCB queue 355. Since SCB 301 is at the head of new SCB queue 355, sequencer 135 moves the value of the SCB site pointer in field Q.sub.-- NEXT into head pointer 310 in SCB site 255. The value of the SCB site pointer is 255, in this example, and so sequencer 135 has also indicated that new SCB queue 355 for host adapter device 120 is now empty.
As described above, appending a SCB to a queue requires multiple operations, as does removing a SCB. By necessity, these operations are separated in time. Because a queue is commonly accessible by both HIM 102 and a sequencer, i.e., by two parties, there can be accesses by one party in between operations of the other party. Problems arise when a queue is accessed by one party while that queue is in the midst of being changed by the other party. For example, sequencer 135 has just removed tail SCB 303 from new SCB queue 355, but has not yet updated tail pointer 311. HIM 102 uses the old value of tail pointer 311 to append a new SCB to new SCB queue 355. The result is that the new SCB is appended to a SCB site that is no longer in new SCB queue 355. Consequently, the appended SCB will never be received by sequencer 135. To eliminate problems such as this, different orders of operations by one party can be tried, but all have their vulnerability to disastrous accesses by the other party.
To prevent errors in management of the queues, both the new SCB queues and the done SCB queue, a token scheme is used to lock one party out of a queue while the other party is modifying the queue. A token, a bit in a register, is commonly accessible by HIM 102 and the sequencer or sequencers that have access to the queue. The token can be taken by one party or the other, but not both. A party must have possession of the token before that party can modify a queue, and must return the token when the party is done operating on the queue.
This scheme insures that one party cannot draw false conclusions about the state of a queue while that queue is being changed by another party. Normally, each queue has a corresponding token register dedicated to that queue. Thus, new SCB queue 355 has a token register within SCB array site 255.
Hence, SCB array site 255 contains head and tail pointers and token registers for new SCB and done SCB queues. For four host adapter devices, each with a new SCB queue and token register, and a shared done SCB queue and token register, the number of queue delimiter and token bytes at SCB site 255 is fifteen.
While this method of SCB management is reliable, the maintenance of the head and tail pointers, and the tokens results in complex queue management. This queue management requires both time for processing and valuable real estate associated with the firmware required for both the HIM and the operations performed by the sequencers. Since the operations being performed are typically associated with managing user data, a SCB queue management method that requires less complexity, is reliable, and reduces processing time is desirable.